Для многих задач наиболее эффективным алгоритмом является почтенный метод Ньютона-Рафсона [1132], [1266]. Это— общий метод поиска корней функций, т.е. метод решения уравнений в форме g(х) =0. Этот алгоритм действует на основе вычисления новой оценки для корня х в соответствии с формулой Ньютона:

Чтобы найти максимум или минимум f, необходимо найти такое значение х, для которого градиент равен нулю (т.е.). Поэтому функция g(х) в формуле

Ньютона принимает вид, и уравнение обновления состояния может быть за-

писано в матрично-векторной форме следующим образом:

где — представляет собой гессиан (матрицу вторых производных), элементы которогозадаются выражением. Поскольку гессиан имеет п2 элементов, то метод Ньютона-Рафсона в многомерных пространствах становится дорогостоящим, поэтому было разработано множество способов приближенного решения этой задачи.

Локальные максимумы, хребты и плато создают затруднения в работе методов локального поиска не только в дискретных пространствах состояний, но и в непрерывных пространствах состояний. Для преодоления этих затруднений могут применяться алгоритмы с перезапуском случайным образом и с эмуляцией отжига, которые часто оказываются достаточно полезными. Тем не менее многомерные непрерывные пространства характеризуются очень большим объемом, в котором легко потеряться.

Последней темой, с которой необходимо кратко ознакомиться, является ^ оптимизация с ограничениями. Задача оптимизации называется задачей оптимизации с ограничениями, если решения в ней должны удовлетворять некоторым жестким ограничениям на значения каждой переменной. Например, в рассматриваемой задаче с размещением аэропортов можно ввести ограничения, чтобы места для аэропортов находились в пределах Румынии, причем на суше (а не, допустим, на середине озера). Сложность задач оптимизации с ограничениями зависит от характера ограничений и от целевой функции. Наиболее широко известной категорией таких задач являются задачи линейного программирования, в которых ограничения должны представлять собой линейные неравенства, образующие выпуклую область, а целевая функция также является линейной. Задачи линейного программирования могут быть решены за время, полиномиально зависящее от количества переменных. Кроме того, проводились исследования задач с другими типами ограничений и целевых функций: квадратичное программирование, коническое программирование второго порядка и т.д.